// 与lca同，不需要遍历整棵树，但是需要对递归返回的值做处理（这样更加方便）
// 利用二叉搜索树的性质
class Solution {
 public:
  TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == NULL) {
      TreeNode* node = new TreeNode(val);
      return node;
    }
    TreeNode* cur = root;
    TreeNode* parent =
        root;  // 这个很重要，需要记录上一个节点，否则无法赋值新节点
    while (cur != NULL) {
      parent = cur;
      if (cur->val > val)
        cur = cur->left;
      else
        cur = cur->right;
    }
    TreeNode* node = new TreeNode(val);
    if (val < parent->val)
      parent->left = node;  // 此时是用parent节点的进行赋值
    else
      parent->right = node;
    return root;
  }
};
/*
class Solution {
private:
    TreeNode* parent;
    void traversal(TreeNode* cur, int val) {
        if (cur == NULL) {
            TreeNode* node = new TreeNode(val);
            if (val > parent->val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = cur;
        if (cur->val > val) traversal(cur->left, val);
        if (cur->val < val) traversal(cur->right, val);
        return;
    }

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
};
// 三种方法
*/